/*
MIT License

Copyright (c) 2021 МГТУ им. Н.Э. Баумана, кафедра ИУ-6, Михаил Фетисов,

https://bmstu.codes/lsx/simodo/loom
*/

#include "simodo/interpret/builtins/hosts/fuze/ParsingTableBuilder_LR1.h"

#include "simodo/inout/convert/functions.h"
#include "simodo/inout/format/fmt.h"

#include <algorithm>
#include <cassert>
#include <cstdint>

namespace simodo::interpret::builtins
{
    // Все улучшения, строго говоря, не соответствуют классу LR1
    // См. тест: 
    // bin/simodo-grammatize -p test/source/grammar lr1-04 -z lr -r -i

    // Улучшение выполнено не корректно.
    #define LR1_IMPROVED_2_no
    // Это улучшение по идее работает корректно
    #define LR1_IMPROVED_1

    namespace {
        uint64_t packPositionKey(size_t rno, size_t pos)
        {
            return rno + pos*UINT32_MAX;
        }

    }


    void ParsingTableBuilder_LR1::fillStateTable()
    {
        parser::FsmState_t state;
        state.emplace_back(parser::FsmStatePosition(0,0,{inout::Lexeme{u"",inout::LexemeType::Empty}}));
        addState(state,0);

        fillState(0);

        _g.build_method = parser::TableBuildMethod::LR1;
    }

    void ParsingTableBuilder_LR1::fillState(size_t state_no)
    {
        // При входе в этот метод в заданном состоянии (state_no) уже определены основные позиции
        // Этот метод вызывается рекурсивно, единожды для каждого состояния

        /// \attention Код данного метода (как и всего данного класса) выполняет активную модификацию
        /// структур грамматики, заданной в параметре _g. Поэтому, крайне не желательно создавать
        /// ссылки на члены класса _g. Массивы могут реаллокироваться. Будьте осторожны.
        /// Работайте с индексами, они не меняются.

        std::multimap<DepthPair,parser::FsmStatePosition,DepthPairComparator>
                                    position_multiset;
        std::map<std::u16string,std::set<inout::Lexeme>>  prod_lookahead_set;

        // Первым делом необходимо дополнить заданное состояние (state_no) "замыканиями",
        // т.е. символами, которые всегда идут в первой позиции для каждой основной позиции.

        assert(state_no < _g.states.size());
        size_t position_initial_count = _g.states[state_no].size(); // размер массива в цикле не является инвариантом (мы его меняем)

        for(size_t i=0; i < position_initial_count; ++i) {
            // Точно известно, что основные позиции состояния добавляются в начало
            if (!_g.states[state_no][i].is_main)
                break;

            size_t rno = _g.states[state_no][i].rule_no;
            size_t pos = _g.states[state_no][i].position;

            assert(rno < _g.rules.size());

            auto it_prod_lookahead = prod_lookahead_set.find(_g.rules[rno].production);

            if (it_prod_lookahead == prod_lookahead_set.end())
                prod_lookahead_set.insert({_g.rules[rno].production,_g.states[state_no][i].lookahead});
            else
                for(const inout::Lexeme & l : _g.states[state_no][i].lookahead)
                    it_prod_lookahead->second.insert(l);

            // Находим замыкания (формируем отсортированный по уровням и продукциям перечень замыканий)
            // Такое предварительное формирование необходимо для достижения симметрии в обработке разных
            // описаний одной и той же грамматики
            if (pos < _g.rules[rno].pattern.size())
                fillClosure(state_no, rno, pos, 0, position_multiset);
        }

        // Записываем отсортированные не основные позиции в наше состояние
        // (теперь внутреннее представление грамматики является инвариантным)
        for(const auto & [key,p] : position_multiset)
            _g.states[state_no].push_back(p);

        // Устанавливаем предпросмотры для всех неосновных позиций
        // (для основных позиций они должны быть заданы перед вызовом метода)

        fillLookahead(state_no, position_initial_count, prod_lookahead_set);

        // Состояния, созданные в результате анализа замыканий (не основных позиций),
        // которые нужно будет заполнить
        std::set<size_t> new_states;

        // Текущее состояние создано, готовим следующие состояния
        // Проходим по всем позициям нашего состояния и для каждого перехода
        // создаем следующее состояние.
        // Проставляем значение next для позиций.

        for(size_t i_pos_in_state=0; i_pos_in_state < _g.states[state_no].size(); ++i_pos_in_state) {
            size_t current_rno = _g.states[state_no][i_pos_in_state].rule_no;
            size_t current_pos = _g.states[state_no][i_pos_in_state].position;

            assert(current_rno < _g.rules.size());
            const parser::GrammarRule & current_rule = _g.rules[current_rno];

            // Важно убедиться, что есть куда переходить
            if (current_pos == current_rule.pattern.size())
                continue;
            // и эта позиция не использована ранее в этом же цикле (не установлено состояние перехода)
            if (_g.states[state_no][i_pos_in_state].next_state_no > 0)
                continue;

            assert(current_pos < current_rule.pattern.size());
            const inout::Lexeme & current_symbol = current_rule.pattern[current_pos];

            // Для символа конца не создаётся новых состояний
            if (current_symbol.type() == inout::LexemeType::Empty )
                continue;

            // Убеждаемся, что нужного основного состояния ещё нет
            size_t find_state = findMainPosition(current_rno, current_pos+1, prod_lookahead_set[_g.rules[current_rno].production]);
            size_t next_state_no;
            if (find_state == 0) // (совпадение с нулевым состоянием невозможно, т.к. оно создаётся искусственно)
            {
                // Точного совпадения не нашли
                // Создаем следующее состояние и нашу следующую основную позицию
                next_state_no = _g.states.size();
                _g.states[state_no][i_pos_in_state].next_state_no = next_state_no;

                parser::FsmState_t new_state;
                new_state.emplace_back(current_rno, current_pos+1, prod_lookahead_set[_g.rules[current_rno].production], true, 0);
                addState(new_state,next_state_no);
                new_states.insert(next_state_no);
            }
            else
                _g.states[state_no][i_pos_in_state].next_state_no = next_state_no = find_state;

            // Находим позицию с тем же переходным символом
            for(size_t i_pos_add=i_pos_in_state+1; i_pos_add < _g.states[state_no].size(); ++i_pos_add) {
                if (_g.states[state_no][i_pos_add].next_state_no != 0)
                    continue;

                size_t add_rno = _g.states[state_no][i_pos_add].rule_no;
                size_t add_pos = _g.states[state_no][i_pos_add].position;

                assert(add_rno < _g.rules.size());
                const parser::GrammarRule & add_rule = _g.rules[add_rno];

                if (add_pos < add_rule.pattern.size())
                    if (current_symbol == add_rule.pattern[add_pos]) {
                        // Проверяем, что такой основной позиции ещё нет
                        bool found = false;
                        auto it = _g.states[next_state_no].begin();
                        for(; it != _g.states[next_state_no].end() && it->is_main; ++it)
                            if (it->rule_no == add_rno) {
                                found = true;
                                break;
                            }
                        // Добавляем основную позицию
                        _g.states[state_no][i_pos_add].next_state_no = next_state_no;
                        if (!found) {
                            _g.states[next_state_no].emplace(it, add_rno,add_pos+1,prod_lookahead_set[_g.rules[add_rno].production],true,0);
                            _position_index.insert({packPositionKey(add_rno,add_pos+1),next_state_no});
                            new_states.insert(next_state_no);
                        }
                    }
            }
        }

        // Вызываем себя рекурсивно, чтобы заполнить созданные основные состояния по аналогии
        for(auto i : new_states)
            fillState(i);
    }

    size_t ParsingTableBuilder_LR1::findMainPosition(size_t rno, size_t pos, const std::set<inout::Lexeme> & lookahead) const
    {
        auto range = _position_index.equal_range(packPositionKey(rno,pos));

        for(auto &it=range.first; it != range.second; ++it)
        {
            size_t               it_state = it->second;
            parser::FsmState_t & state    = _g.states[it_state];

            for(size_t it_pos=0; it_pos < state.size(); ++it_pos)
            {
                parser::FsmStatePosition & p = state[it_pos];

                // Проверяем только основные позиции, и они всегда в начале
                if (!p.is_main)
                    break;

                if (rno == p.rule_no && pos == p.position)
                {
    #ifdef LR1_IMPROVED_2
                    // Улучшение выполнено не корректно. См. тест:
                    // bin/simodo-grammatize -p test/source/grammar lr1-04 -z lr -r -i

                    if (pos == _g.rules[rno].pattern.size()) {
                        // Данный алгоритм выполняет рекомендацию \todo ниже.
                        // Можно безопасно слить состояния закрываемых позиций одного правила из разных предпросмотров
                        bool is_only_last_positions = true;
                        if (state.size() > 1)
                            for(size_t i=0; i < state.size(); ++i)
                                if (state[i].position != _g.rules[state[i].rule_no].pattern.size()) {
                                    is_only_last_positions = false;
                                    break;
                                }

                        if (is_only_last_positions) {
                            for(const Lexeme & l : lookahead)
                                p.lookahead.insert(l);
                            return it_state;
                        }
                    }
    #elif defined (LR1_IMPROVED_1)
                    if (pos == _g.rules[rno].pattern.size()
                        /// \todo Данный алгоритм осторожничает, не оптимизируя случаи нескольких основных закрываемых позиций.
                        /// Можно ещё немного оптимизировать количество состояний без потери качества, если разрешать слияние с
                        /// не единственными закрываемыми позициями.
                        /// Для этого в состоянии не должно быть незакрываемых позиций (и все позиции должны быть основными?).
                        && state.size() == 1)
                    {
                        for(const inout::Lexeme & l : lookahead)
                            p.lookahead.insert(l);
                        return it_state;
                    }
    #endif
                    if (lookahead == p.lookahead)
                        return it_state;
                }
            }
        }

        return 0;
    }

    void ParsingTableBuilder_LR1::fillClosure(size_t state_no, size_t rno, size_t pos, int depth,
                                        std::multimap<DepthPair, parser::FsmStatePosition, DepthPairComparator> &position_multiset)
    {
        auto production_range = _production_index.equal_range(_g.rules[rno].pattern[pos].lexeme());

        // Просматриваем продукции заданного символа
        for(auto &it=production_range.first; it != production_range.second; ++it)
        {
            size_t next_rno = it->second;

            bool find = false;
            for(auto & [key_depth,p] : position_multiset)
                if (p.rule_no == next_rno && p.position == 0)
                {
                    find = true;
                    break;
                }

            if (!find)
            {
                int find_depth = INT32_MAX;
                for(auto & [key_depth,p] : position_multiset)
                    if (_g.rules[p.rule_no].production == _g.rules[next_rno].production)
                    {
                        find_depth = key_depth.depth;
                        break;
                    }

                if (find_depth > depth)
                    find_depth = depth;

                position_multiset.insert({{find_depth,_g.rules[next_rno].pattern.size()},parser::FsmStatePosition(next_rno, 0, false, 0)});
                fillClosure(state_no, next_rno, 0, depth+1, position_multiset);
            }
        }
    }

    void ParsingTableBuilder_LR1::fillLookahead(size_t state_no, size_t position_initial_count, std::map<std::u16string,std::set<inout::Lexeme>> & prod_lookahead_set)
    {
        assert(state_no < _g.states.size());

        for(size_t i=position_initial_count; i < _g.states[state_no].size(); ++i)
        {
            size_t rno = _g.states[state_no][i].rule_no;

            assert(rno < _g.rules.size());

            std::set<inout::Lexeme> lookahead;

            for(size_t parent=0; parent < i; ++parent)
            {
                size_t prev_rno = _g.states[state_no][parent].rule_no;
                size_t prev_pos = _g.states[state_no][parent].position;

                if(prev_pos < _g.rules[prev_rno].pattern.size())
                    if(_g.rules[prev_rno].pattern[prev_pos].lexeme() == _g.rules[rno].production)
                    {
                        if (prev_pos == _g.rules[prev_rno].pattern.size()-1)
                        {
                            // Последний элемент
                            for(const inout::Lexeme & l : _g.states[state_no][parent].lookahead)
                                lookahead.insert(l);
                        }
                        else if (_g.rules[prev_rno].pattern[prev_pos+1].type() != inout::LexemeType::Compound)
                        {
                            // Следующий элемент является терминалом и определяет предпросмотр
                            lookahead.insert(_g.rules[prev_rno].pattern[prev_pos+1]);
                        }
                        else
                        {
                            // Определяем терминалы, с которых может начинаться следующий нетерминал
                            std::set<inout::Lexeme> processed;
                            fillStartingTerminalsByProd(_g.rules[prev_rno].pattern[prev_pos+1], lookahead, processed);
                        }
                    }
            }

            auto it_prod_lookahead = prod_lookahead_set.find(_g.rules[rno].production);

            if (it_prod_lookahead == prod_lookahead_set.end())
                prod_lookahead_set.insert({_g.rules[rno].production,lookahead});
            else
                for(const inout::Lexeme & l : lookahead)
                    it_prod_lookahead->second.insert(l);

            _g.states[state_no][i].lookahead = prod_lookahead_set[_g.rules[rno].production];
        }
    }

    void ParsingTableBuilder_LR1::fillStartingTerminalsByProd(const inout::Lexeme &prod, std::set<inout::Lexeme> &terminals, std::set<inout::Lexeme> &processed)
    {
        auto range = _production_index.equal_range(prod.lexeme());

        // Просматриваем продукции заданного символа
        for(auto &it=range.first; it != range.second; ++it) {
            size_t rno = it->second;
            const inout::Lexeme & pattern0 = _g.rules[rno].pattern[0];

            if (pattern0.type() != inout::LexemeType::Compound) {
                if (terminals.end() == terminals.find(pattern0))
                    terminals.insert(pattern0);
            }
            else if (pattern0 != prod)
                if (processed.end() == processed.find(pattern0)) {
                    processed.insert(pattern0);
                    fillStartingTerminalsByProd(pattern0,terminals,processed);
                }
        }
    }

    bool ParsingTableBuilder_LR1::fillParseTable()
    {
        bool success = true;

        for(size_t i_state=0; i_state < _g.states.size(); ++i_state)
        {
            const parser::FsmState_t &state = _g.states.at(i_state);

            // Сдвиги имеют больший приоритет (правоассоциативная грамматика)
            for(const parser::FsmStatePosition &p : state)
                if (const parser::GrammarRule & r = _g.rules.at(p.rule_no); p.position < r.pattern.size())
                {
                    const inout::Lexeme & s = r.pattern.at(p.position);

                    if (p.next_state_no == 0)    // 0 не в последней позиции означает завершение
                    {
                        if (s.type() == inout::LexemeType::Empty)
                        {
                            // Принятие (acceptance)
                            if (!insertValue(i_state, _g.getColumnIndex(s), _g.packFsmValue(parser::FsmActionType::Acceptance,0)))
                                success = false;
                        }
                        else
                            assert(false);
                    }
                    else
                        // p.next != 0 означает наличие перехода в соотв-щее состояние НКА
                        // Сдвиг (shift)
                        if (!insertValue(i_state, _g.getColumnIndex(s), _g.packFsmValue(parser::FsmActionType::Shift,static_cast<size_t>(p.next_state_no))))
                            success = false;

                    if (_need_to_break)
                        return false;
                }

            // Свёртки обрабатываем позже, чтобы при конфликтах принимать сдвиги
            // Правила по умолчанию правоассоциативные
            // (свёртки не будут записываться в таблицу, если соотв. позиция занята; кроме правил, помеченных как левоассациативные)
            for(const parser::FsmStatePosition &p : state)
            {
                if (!p.is_main)    // В свёртке могут участвовать только основные позиции, которые находятся всегда в начале списка
                    break;

                if (p.rule_no == 0 || p.next_state_no != 0)
                    continue;

                const parser::GrammarRule &r = _g.rules.at(p.rule_no);

                assert(p.position == r.pattern.size());

                // Свёртка (reduce)

                for(const inout::Lexeme & s : p.lookahead)
                    if (!insertValue(i_state, _g.getColumnIndex(s), _g.packFsmValue(parser::FsmActionType::Reduce,p.rule_no)))
                        success = false;

                if (_need_to_break)
                    return false;
            }
        }

        return success;
    }

    bool ParsingTableBuilder_LR1::insertValue(size_t line, size_t column, parser::Fsm_value_t value)
    {
        if (!_g.findFsmValue(line,column))
        {
            // Заданный вариант обработки отсутствует в таблице разбора - просто добавляем
            _g.parse_table.emplace(_g.packFsmKey(line,column),value);
            return true;
        }

        parser::Fsm_value_t exist_value = _g.getFsmValue(line,column);

        parser::FsmActionType exist_action = _g.unpackFsmAction(exist_value);
        parser::FsmActionType new_action   = _g.unpackFsmAction(value);

        // Если вариант обработки в таблице совпадает с заданным - всё ОК
        if (exist_action == new_action && exist_value == value)
            return true;

        // Вариант обработки существует в таблице разбора и он отличается от нашего - нужно принять решение какой из них использовать

        const inout::Lexeme & s = _g.columns.at(column);

        size_t exist_location = _g.unpackFsmLocation(exist_value);
        size_t new_location   = _g.unpackFsmLocation(value);

        std::string sout = inout::fmt("%1'. Состояние %2, символ %3 (#%4). Конфликтуют %5%6 и %7%8. ")
                            .arg(_grammar_name)
                            .arg(line)
                            .arg(inout::getLexemeMnemonic(s))
                            .arg(column)
                            .arg(parser::getFsmActionChar(exist_action))
                            .arg(exist_location)
                            .arg(parser::getFsmActionChar(new_action))
                            .arg(new_location);

        const inout::Token & t = (new_action == parser::FsmActionType::Shift)
                ? _rules[1].pattern[0]
                : _rules[new_location].pattern[_rules[new_location].pattern.size()-1];

        if (exist_action == parser::FsmActionType::Shift && new_action == parser::FsmActionType::Reduce)
        {
            assert(new_location < _g.rules.size());
            assert(new_location < _rules.size());
            if (_g.rules[new_location].reduce_direction == parser::RuleReduceDirection::RightAssociative)
            {
                sout += inout::fmt("Принят %1%2.")
                            .arg(parser::getFsmActionChar(exist_action))
                            .arg(exist_location);
            }
            else
            {
                _g.parse_table.at(_g.packFsmKey(line,column)) = value;
                sout += inout::fmt("Принят %1%2.")
                            .arg(parser::getFsmActionChar(new_action))
                            .arg(new_location);
            }

            if (_g.rules[new_location].reduce_direction == parser::RuleReduceDirection::Undefined)
                _m.reportError( t.makeLocation(files()), 
                                inout::fmt("Неоднозначность грамматики '%1").arg(sout));

            return true;
        }

        if (_number_of_collisions == COLLISIONS_LIMIT) {
            _m.reportError( t.makeLocation(files()),
                            inout::fmt("Количество коллизий превысило предел (%1), работа прервана")
                            .arg(COLLISIONS_LIMIT));
            _need_to_break = true;
            return false;
        }

        _m.reportError( t.makeLocation(files()), 
                        inout::fmt("Критическая неоднозначность грамматики '%1").arg(sout));

        _number_of_collisions++;

        return !_strict_rule_consistency;
    }

    void ParsingTableBuilder_LR1::addState(parser::FsmState_t state, size_t state_no)
    {
        _g.states.emplace_back(state);

        for(const parser::FsmStatePosition & p : state)
        {
            if (!p.is_main)
                break;

            _position_index.insert({packPositionKey(p.rule_no,p.position),state_no});
        }
    }

}